package com.sx.sx1.lintcode.day717;

public class LC221 {


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    static class Solution {
        /**
         * @param l1: The first list.
         * @param l2: The second list.
         * @return: the sum list of l1 and l2.
         */
        public ListNode addLists2(ListNode l1, ListNode l2) {
            ListNode node1 = reverse(l1);
            ListNode node2 = reverse(l2);

            ListNode ans = new ListNode(-1);
            ListNode tail = ans;
            boolean add = false;
            while (node1 != null && node2 != null) {

                int a = node1.val;
                int b = node2.val;

                int sum = a + b;
                if (add) {
                    sum += 1;
                }

                if (sum >= 10) {
                    add = true;
                    sum = sum % 10;
                } else {
                    add = false;
                }

                tail.next = new ListNode(sum);
                tail = tail.next;

                node1 = node1.next;
                node2 = node2.next;
            }


            while (node1 != null) {

                int a = node1.val;


                int sum = a;
                if (add) {
                    sum += 1;
                }

                if (sum >= 10) {
                    add = true;
                    sum = sum % 10;
                } else {
                    add = false;
                }

                tail.next = new ListNode(sum);
                tail = tail.next;

                node1 = node1.next;
            }

            while (node2 != null) {

                int a = node2.val;


                int sum = a;
                if (add) {
                    sum += 1;
                }

                if (sum >= 10) {
                    add = true;
                    sum = sum % 10;
                } else {
                    add = false;
                }

                tail.next = new ListNode(sum);
                tail = tail.next;

                node2 = node2.next;
            }

            if (add) {
                tail.next = new ListNode(1);
            }
            ListNode rnode = ans.next;
            return reverse(rnode);
        }

        public ListNode reverse(ListNode node) { //翻转连表
            ListNode pre = null;
            while (node != null) {
                ListNode next = node.next;
                node.next = pre;
                pre = node;
                node = next;
            }

            return pre;
        }

    }


}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有189条未读消息，请及时查看
221 · 链表求和 II
算法
中等
通过率
32%

题目
题解26
笔记
讨论99+
排名
记录
描述
假定用链表表示两个数，其中每个节点仅包含一个数字。假设这两个数的数字顺序排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入: 6->1->7   2->9->5
输出: 9->1->2
样例 2:

输入: 1->2->3   4->5->6
输出: 5->7->9
相关知识
学习《2024年3月北美大厂最新面试真题精讲》课程中的4.7Mircosoft：最新面试精选004相关内容 ，了解更多相关知识！
标签
企业
Bloomberg
Microsoft
相关题目

756
两数相乘
简单

655
大整数加法
简单

35
翻转链表（一）
简单

656
大整数乘法
中等

167
链表求和
简单
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
213/1857
已开启智能提示
发起考试
30 分 00 秒
12345678910111213141516171819202122
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }

控制台
历史提交

 */